package leetcode;

/**
 * @Project : algorithm-learning-java
 * @Package : leetcode
 * @Author : Ruoyu Wang
 * @User : Momenta
 * @DateTime : 2024/1/16 17:33
 */
public class Q0005 {
    public String longestPalindrome(String s) {
        int res = 1;
        int l = 0, r = 1;
        int[][] f = new int[s.length() + 1][s.length() + 1];
        for (int len = 1; len <= s.length(); len++) {
            for (int i = 0, j = i + len; j <= s.length(); i++, j++) {
                if (i + 1 == j) {
                    f[i][j] = 1;
                    continue;
                }
                if (s.charAt(i) == s.charAt(j - 1)) {
                    f[i][j] = f[i + 1][j - 1] + 2;
                } else {
                    f[i][j] = -0x3f3f3f3f;
                }
                if (f[i][j] > res) {
                    res = f[i][j];
                    l = i;
                    r = j;
                }
            }
        }
        return s.substring(l, r);
    }

    public static void main(String[] args) {
        Q0005 sl = new Q0005();
        System.out.println(sl.longestPalindrome("aacabdkacaa"));
    }
}
